﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class Solution560
{
    //暴力一下
    public int SubarraySum2(int[] nums, int k)
    {
        int count = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            int sum = 0;

            for (int j = i; j < nums.Length; j++)
            {



                sum += nums[j];

                if (sum == k)
                {
                    count++;
                }


                //if (sum > k)//不能剪纸，有负数
                //{
                //    break;
                //}


            }


        }
        return count;
    }

    //前缀和
    public int SubarraySum(int[] nums, int k)
    {

        int count = 0;
        int len = nums.Length;
        int[] presum = new int[len];
        presum[0] = nums[0];

        int pre = 0;

        Dictionary<int, int> map = new Dictionary<int, int>();

        map.Add(k, 0);//前缀和等于k的也符合要求

        for (int i = 0; i < len; i++)//i是结尾的index
        {


            pre += nums[i];
            Console.WriteLine(pre);
            if (map.ContainsKey(pre-k))//以i为结尾的，符合要求的数组可能有好几个
            {
                count += map[pre - k];
            }


            if (!map.ContainsKey(pre ))
            {
                map[pre ] = 1;
            }
            else
            {
                map[pre ] = map[pre] + 1;
            }








        }
        // presum[i]- presum[j-1]=k,就是我们要找的一个子数组，
        //问题转换为两数之和


        return count;





    }
}

class Program560
{

    static void Main560(string[] args)
    {

        Solution560 solution = new Solution560();
        int[] nums = [1, 1, 1];
        int k = 2;

        int res = solution.SubarraySum(nums, k);
        Console.WriteLine(res);
    }

}